1. Field of the Invention
Apparatuses and methods consistent with the present invention relate to a demand paging technique, and more particularly, to a technique for reducing the page replacement time in a system using such a demand paging technique.
2. Description of the Related Art
The demand paging technique is a technique of allocating a virtual memory to an auxiliary storage device, such as a hard disk, in an operating system using a virtual memory system and to perform physical memory mapping in accordance with a user's request so as to efficiently use a limited main memory. A flash memory is nonvolatile and is rapidly accessed, like the hard disk, with low power consumption. Accordingly, the flash memory has been applied to an embedded system or a mobile device.
The procedure of demand paging is as follows. When a page fault occurs, a page fault handler first secures a physical memory space for loading the corresponding page having the page fault. When there is no available physical memory space, the page fault handler replaces the corresponding page with a page allocated beforehand so as to secure the physical memory space. After securing the physical memory space, the fault handler searches an address of the nonvolatile storage device in which the page having the page fault is stored. Then, the fault handler reads the corresponding page from the nonvolatile storage device and updates a memory mapping table.
FIG. 1 is a diagram showing a demand paging process according to the relationship between a software process and a device I/O with respect to time.
Data is read from a device when the page fault occurs. A page fault handler 10 first reads data from the device and secures a memory space for storing the data. Then, the page fault hander 10 searches an address of the page having the page fault and creates a command READ_CMD so as to read data of the corresponding page. When the command is transmitted to the device, the device transmits the data after a time corresponding to a busy time passes. The busy time is the time required for performing a preceding operation so as to read the data stored in the corresponding page. For example, when data is read from a flash memory, a column signal and a row signal are transmitted to a region in which the corresponding page is stored, to thereby read the corresponding data. It takes time to perform the above-described processes. After this time passes, the data of the corresponding page can be transmitted from the flash memory. When the data is transmitted from the device, the page fault handler updates the mapping table and stores the received data.
Referring to FIG. 1, the page replacement operation needs a plurality of processes, for example, of reading data from the device and arranging a page fault result, and thus the reduction in the number of page replacement times may have a large effect on system performance.
A Least Recently Used (LRU) algorithm can be exemplified as the optimum page replacement algorithm. The LRU algorithm is a method that determines a page least recently used as a target of the replacement. However, in order to apply an LRU page replacement policy to demand paging, hardware support is required. However, there is no hardware support for the LRU page replacement policy in most systems. Therefore, an algorithm, such as a clock algorithm or Mach 2.5, similar to the LRU algorithm, has been generally used.
The known paging techniques process demand paging on the basis of a nonvolatile storage device, such as a hard disk, but do not consider the characteristics of the nonvolatile storage device, such as a flash memory. A method of reading data from a hard disk is different from a method of reading data from a flash memory. However, in the paging technique, this difference is not considered.
In case of the hard disk, data can be read from a nonvolatile storage device to a physical memory by using addresses of the physical memory and the nonvolatile storage device. However, in case of the nonvolatile storage device, such as a flash memory, having a buffer (or register) in a device, data should be loaded to the buffer (or register) in the nonvolatile storage device before reading the data into the physical memory (RAM). Then, the data is loaded to the physical memory from the buffer or register. In the flash memory, if a read command is issued with an address of the nonvolatile storage device, the data is loaded to the buffer (register) after the read command is issued. When the data is loaded, the device is in a busy state. Generally, the time of the busy state is usually 23 μsec to 35 μsec but varies according to the flash memories.
Other than the above-described cases, when the paging technique is applied, unnecessary operations may be continuously repeated. Therefore, a method and apparatus for reducing a page replacement time in demand paging is desired.